import java.lang.System;
import java.util.HashMap;
import java.util.Map;
import java.lang.String;

/**
 * 最长不重复子字符串
 */
public class LongestUniqueSubstring {

    // 动态规划+线性遍历
    public int solution3(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for (int j = 0; j < s.length(); j++) {
            int i = j -1;
            while(i >= 0 && s.charAt(i) != s.charAt(j)) i--;
            tmp = tmp < j - i ? tmp + 1 : j -i;
            res = Math.max(res, tmp);
        }
        return res;
    }

    // 动态规划+哈希表
    public int solutio2(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for (int j = 0; j < s.length(); j++) {
            int i = dic .getOrDefault(s.charAt(j), -1);
            dic.put(s.charAt(j), j);
            tmp = tmp < j -i ? tmp +1 : j -i;
            res = Math.max(res, tmp);
        }
        return res;
    }

    // 双指针+哈希表
    public int solution(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        // 
        int res = 0, tmp = 0, i = -1;
        for(int j = 0; j <  s.length(); j++) {
            if(dic.containsKey(s.charAt(j))) {
                i = dic.get(s.charAt(j)); // 获取索引i
            }
            dic.put(s.charAt(j), j);
            tmp = tmp < j - i ? tmp + 1 : j - i;
            res = Math.max(res, tmp);
        }
        return res;
    }

    public static void main(String[] args) {
        String data = "abcdaefghdijk"; // "iernewsergge";
        int result = new LongestUniqueSubstring().solution(data);
        System.out.print("result: " + result);
        System.out.print("\nsubstring: " + data.substring(0, result));
    }
}
